#include <iostream>
#include <vector>
#include <climits>

using namespace std;

struct Edge {
    int start{};
    int end{};
    int weight{};
};

const int UNKNONW = INT_MAX;
vector<Edge> edges;
int V, E;

int GetMinDistance(vector<int>& distance, vector<bool>& visited) {
    int minDistance = UNKNONW;
    int result;
    for (int v = 0; v < distance.size(); ++v) {
        if (!visited[v] && distance[v] <= minDistance)
            minDistance = distance[v], result = v;
    }
    return result;
}

vector<int> Dijkstra(int V, int start, vector<Edge>& edges) {
    vector<int> distance(V, UNKNONW);
    vector<bool> visited(V, false);
    distance[start] = 0;
    for (int i = 0; i < V - 1; ++i) {
        int currentNode = GetMinDistance(distance, visited);
        visited[currentNode] = true;
        for (auto& e : edges) {
            if (e.start != currentNode) continue;
            if (visited[e.end]) continue;
            if (distance[currentNode] != UNKNONW && distance[currentNode] + e.weight < distance[e.end])
                distance[e.end] = distance[currentNode] + e.weight;
        }
    }
    return distance;
}

bool HasNegativeCycle(const vector<int>& distance, const vector<Edge>& edges) {
    for (const auto& e : edges) {
        int u = e.start;
        int v = e.end;
        int w = e.weight;
        if (distance[u] == UNKNONW) continue;
        if (distance[u] + w < distance[v])
            return true;
    }
    return false;
}

vector<int> BellmanFord(int V, vector<Edge>& edges) {
    vector<int> distance(V + 1, UNKNONW);
    int s = V;
    for (int i = 0; i < V; ++i) {
        edges.emplace_back(Edge{s, i, 0});
    }
    distance[s] = 0;
    for (int i = 1; i < V; ++i) {
        for (const auto& e : edges) {
            int u = e.start;
            int v = e.end;
            int w = e.weight;
            if (distance[u] == UNKNONW)
                continue;
            if (distance[u] + w < distance[v])
                distance[v] = distance[u] + w;
        }
    }

    if (HasNegativeCycle(distance, edges)) {
        cout << "found negative cycle\n";
        return {};
    }

    return distance;
}

void Johnson(int V, vector<Edge>& edges) {
    //先用Bellman-Ford求出所有顶点到起点的路径
    vector<int> d = BellmanFord(V, edges);
    if (d.empty()) return;
    //将所有边权调整为非负
    for (int i = 0; i < edges.size(); ++i) {
        edges[i].weight += (d[edges[i].start] - d[edges[i].end]);
    }
    //遍历所有顶点，用Dijkstra求解到每个顶点的最短路径
    vector<vector<int>> shortest(V);
    for (int i = 0; i < V; ++i) {
        shortest[i] = Dijkstra(V, i, edges);
    }
    //遍历输出每个顶点到其他顶点的最短路径
    for (int i = 0; i < V; ++i) {
        cout << i << ":\n";
        for (int j = 0; j < V; ++j) {
            shortest[i][j] += d[j] - d[i];
            cout << "\t" << j << ": " << shortest[i][j] << endl;
        }
    }
}

int main(int argc, const char** argv) {
    int V, E;
    cin >> V >> E;
    vector<Edge> edges;
    edges.reserve(E);
    for (int i = 0; i < E; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        edges.emplace_back(Edge{a, b, w});
    }
    Johnson(V, edges);
    return 0;
}